package pri.zjy.array.binarySearch;

/**
 * @author zhangjy
 * @description 搜索插入位置
 * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 * <p>
 * 请必须使用时间复杂度为 O(log n) 的算法。
 * <p>
 * <p>
 * <p>
 * 示例 1:
 * <p>
 * 输入: nums = [1,3,5,6], target = 5
 * 输出: 2
 * 示例 2:
 * <p>
 * 输入: nums = [1,3,5,6], target = 2
 * 输出: 1
 * 示例 3:
 * <p>
 * 输入: nums = [1,3,5,6], target = 7
 * 输出: 4
 * <p>
 * <p>
 * 提示:
 * <p>
 * 1 <= nums.length <= 104
 * -104 <= nums[i] <= 104
 * nums 为 无重复元素 的 升序 排列数组
 * -104 <= target <= 104
 * @date 2025/2/12 17:11
 */
public class SearchInsert_35 {

    public static void main(String[] args) {
        SearchInsert_35 searchInsert35 = new SearchInsert_35();
//        int[] nums = {-1, 0, 3, 5, 9, 12};
        int[] nums = {1, 3, 5, 6};
        int target = 7;
//        int target = 9;
        System.out.println(searchInsert35.searchInsert01(nums, target));
        System.out.println(searchInsert35.searchInsert02(nums, target));


    }

    /**
     * 二分法（个人解法）类似dmsxl；
     * dmsxl解法：最后returnright+1，思想和该方法相同，模拟发现left、right+1都能处理target在所有元素之前、之后的情况
     */

    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1, mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (target < nums[mid]) {
                // 左移
                right = mid - 1;
            } else if (target > nums[mid]) {
                // 左移
                left = mid + 1;
            } else {
                return mid;
            }
        }

        // 模拟会发现，当target最小或最大，left记录的0或nums.length，满足题目
        return left;
    }

    // 暴力解法 T(n) = O(n) , S(n) = O(n)
    public int searchInsertViolent(int[] nums, int target) {
        // 两种情况：找得到和找不到；
        // 1.找得到，直接返回下标i；
        // 2.找不到，当找到nums中第一个大于target的元素，直接返回其下标i，也就是待插入位置；
        // 3.找不到，且nums没有更大元素，则插入尾部

        for (int i = 0; i < nums.length; i++) {
            // 1、2
            if (nums[i] >= target) {
                return i;
            }
        }
        // 3.尾部
        return nums.length;
    }

    /**
     * 分析
     *      1.题目要求，查找指定元素在数组中的位置，若无则返回应该插入的位置下标；
     *      2.升序、无重复数组；
     *      3.数组大小为：1 <= nums.length <= 104，且要求算法时间复杂度为 O(log n)；
     *      结合2、3点——>考虑二分查找；
     *          （1）找得到——》返回对应下标；
     *          （2）找不到——》判断最后nums[left]和target大小，再决定插入位置为left+1 还是left
     */
    public int searchInsert01(int[] nums, int target) {
        // 左闭右闭
        int left = 0, right = nums.length - 1, mid;
        while (left <= right) {
            mid = left + (right - left) / 2;
            if (target < nums[mid]) {
                right = mid - 1;
            } else if (target > nums[mid]) {
                left = mid + 1;
            } else {
                return mid;
            }
        }

        // 跳出循环后，根据最后一个有效区间的left判断插入位置
        // 插入最后一个位置特殊处理，避免数组越界；
        if (left == nums.length) {
            return left;
        }
        if (target > nums[left]) {
            left++;
        }
        return left;
    }

    public int searchInsert02(int[] nums, int target) {
        // 左闭右开
        int left = 0, right = nums.length, mid;
        while (left < right) {
            mid = left + (right - left) / 2;
            if (target < nums[mid]) {
                right = mid;
            } else if (target > nums[mid]) {
                left = mid + 1;
            } else {
                return mid;
            }
        }

        // 跳出循环后，根据最后一个有效区间的left判断插入位置
        // 插入最后一个位置特殊处理，避免数组越界；
        if (left == nums.length) {
            return left;
        }
        if (target > nums[left]) {
            left++;
        }
        return left;
    }

}
